МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра ЕОМ Використання евристичної функції для створення гри Методичні вказівки до лабораторної роботи № 2 з курсу: “Системи штучного інтелекту” для студентів Затверджено на засіданні кафедри “Електронних обчислювальних машин” Протокол № Від 2003 р. Львів 2003 Використання евристичної функції для створення гри. Методичні вказівки до лабораторної роботи № 2 з курсу: “Системи штучного інтелекту” для студентів , 16 с. Укладач: Ємець В.Ф., професор, д.т.н. Сокіл В.М., асистент Юрчак І.Ю, доцент, к.т.н. Відповідальний за випуск: Кремінь В.Т., ст. викладач кафедри ЕОМ Рецензенти: Березко Л.О., доцент кафедри ЕОМ, к.т.н. Каркульовський В.І., доцент кафедри АСУ, к.т.н. 1. Мета роботи Cтворення зразку евристичної функції, яка описує стан укладанки, що полягає у складанні в зростаючому порядку цифр від 1 до 8. Створений алгоритм має за мету розв’язання гри при мінімально можливій кількості кроків, а також розпізнавання станів, у яких гра не має розв’язку. Початковий стан гри встановлюється випадковим чином. Головними елементами евристичної функції є складові підрахунку відстаней вибраних елементів від їх попереднього місця. 2. Теоретичні відомості Алгоритм гри є простим і базується на 3 засадах Підраховане значення евристичної функції відбиває єдиний можливий крок, що залежить від розташування нульового елементу і для якого значення функції є мінімальним (нескінченне від біжучого значення функції) Не варто повторювати попередній крок, якщо він призводить до заплутування алгоритму, і відповідно, не скорочує кількість кроків Нульове значення евристичної функції означає, що даний стан гри є кінцевим станом (елементи є укладеними або їх укладання є неможливим) Стан гри описаний 9-елементною таблицею Tab[8] цілих цифр в полях пронумерованих від 0 до 8 Приймемо наступну послідовність алгоритму: Етап 1 Початковою метою гри є уставляння одиниці на першому місці (в таблиці це поле з номером 0). Відповідно, цей порядок повинен мати найбільший приоритет, тобто йому має відповідати складова, що має найбільшу вагу в моделі функції. Ось ця складова: wartosc+=1000000*abs(miejsce[1]%3-szukana%3); //розглядання нормованої метрики по горизонталі wartosc+=1000000*abs(miejsce[1]/3-szukana/3); //розглядання нормованої метрики по вертикалі Де значення змінної szukana в цей момент дорівнює 0. Найбільша вага цієї складової у зразку евристичної функції доводить, що цей елемент ніколи не буде пересунуто зі свого місця. На цьому етапі гри нульове поле прагне до нульового місця таблиці елементів wartosc+=abs(miejsce[0]%3-szukana%3); //розглядання нормованої метрики по горизонталі wartosc+=abs(miejsce[0]/3-szukana/3); //розглядання нормованої метрики по вертикалі Етап 2 Наступний крок полягає у встановленні 2 і 3 на свої місця. Очевидно евристична функція намагається встановити їх відповідно стану: Де х означає поле замін перед випадковим укладанням залишкових цифр 4,5,6,7,8 Цей етап описує наступний фрагмент коду: //відповідає за 2 wartosc+=100000*abs(miejsce[2]%3-(szukana+2)%3); //розглядання нормованої метрики по горизонталі wartosc+=100000*abs(miejsce[2]/3-(szukana+2)/3); //розглядання нормованої метрики по вертикалі //відповідає за 3 wartosc+=10000*abs(miejsce[3]%3-(szukana+5)%3); //розглядання нормованої метрики по горизонталі wartosc+=10000*abs(miejsce[3]/3-(szukana+5)/3); //розглядання нормованої метрики по вертикалі Елемент 2 має більшу вагу ніж 3, і його варто поставити на власну позицію першим. На цьому етапі нульове поле прагне до першого елементу таблиці. if (Tab[0]==1) szukana++; //до уставляння 2 i 3 у рядку wartosc+=abs(miejsce[0]%3-szukana%3); //розглядання нормованої метрики по горизонталі wartosc+=abs(miejsce[0]/3-szukana/3); //розглядання нормованої метрики по вертикалі тобто значення змінної szukana буде зараз 1. Зауважимо, що у момент гри п...